﻿// --------------------------------------------------------------------------------------------------------------------
// <copyright company="" file="TopologicalSorter.cs">
//   
// </copyright>
// <summary>
//   The TopologicSortable interface.
// </summary>
// --------------------------------------------------------------------------------------------------------------------
namespace Skymate.Collections
{
    using System;
    using System.Collections.Generic;
    using System.Linq;

    /// <summary>
    /// The TopologicSortable interface.
    /// </summary>
    /// <typeparam name="TKey">
    /// </typeparam>
    public interface ITopologicSortable<TKey>
    {
        /// <summary>
        ///     Gets the key.
        /// </summary>
        TKey Key { get; }

        /// <summary>
        ///     Gets the depends on.
        /// </summary>
        TKey[] DependsOn { get; }
    }

    /// <summary>
    ///     The topological sort extensions.
    /// </summary>
    public static class TopologicalSortExtensions
    {
        /// <summary>
        /// The sort topological.
        /// </summary>
        /// <param name="items">
        /// The items.
        /// </param>
        /// <typeparam name="T">
        /// </typeparam>
        /// <returns>
        /// The <see cref="ITopologicSortable"/>.
        /// </returns>
        public static ITopologicSortable<T>[] SortTopological<T>(this ITopologicSortable<T>[] items)
        {
            return SortTopological(items, null);
        }

        /// <summary>
        /// The sort topological.
        /// </summary>
        /// <param name="items">
        /// The items.
        /// </param>
        /// <param name="comparer">
        /// The comparer.
        /// </param>
        /// <typeparam name="T">
        /// </typeparam>
        /// <returns>
        /// The <see cref="ITopologicSortable"/>.
        /// </returns>
        public static ITopologicSortable<T>[] SortTopological<T>(
            this ITopologicSortable<T>[] items, 
            IEqualityComparer<T> comparer)
        {
            Guard.ArgumentNotNull(() => items);

            var sortedIndexes = SortIndexesTopological(items, comparer);
            var sortedList = new List<ITopologicSortable<T>>(sortedIndexes.Length);

            for (var i = 0; i < sortedIndexes.Length; i++)
            {
                // sortedList[i] = items[sortedIndexes[i]];
                sortedList.Add(items[sortedIndexes[i]]);
            }

            return sortedList.ToArray();
        }

        /// <summary>
        /// The sort indexes topological.
        /// </summary>
        /// <param name="items">
        /// The items.
        /// </param>
        /// <typeparam name="T">
        /// </typeparam>
        /// <returns>
        /// The <see cref="int[]"/>.
        /// </returns>
        public static int[] SortIndexesTopological<T>(this ITopologicSortable<T>[] items)
        {
            return SortIndexesTopological(items, null);
        }

        /// <summary>
        /// The sort indexes topological.
        /// </summary>
        /// <param name="items">
        /// The items.
        /// </param>
        /// <param name="comparer">
        /// The comparer.
        /// </param>
        /// <typeparam name="T">
        /// </typeparam>
        /// <returns>
        /// The <see cref="int[]"/>.
        /// </returns>
        public static int[] SortIndexesTopological<T>(this ITopologicSortable<T>[] items, IEqualityComparer<T> comparer)
        {
            Guard.ArgumentNotNull(() => items);

            if (items.Length == 0)
            {
                return new int[] { };
            }

            if (comparer == null)
            {
                comparer = EqualityComparer<T>.Default;
            }

            var sorter = new TopologicalSorter(items.Length);
            var indexes = new Dictionary<T, int>(comparer);

            // add vertices
            for (var i = 0; i < items.Length; i++)
            {
                indexes[items[i].Key] = sorter.AddVertex(i);
            }

            // add edges
            for (var i = 0; i < items.Length; i++)
            {
                if (items[i].DependsOn != null)
                {
                    for (var j = 0; j < items[i].DependsOn.Length; j++)
                    {
                        if (indexes.ContainsKey(items[i].DependsOn[j]))
                        {
                            sorter.AddEdge(i, indexes[items[i].DependsOn[j]]);
                        }
                    }
                }
            }

            var result = sorter.Sort().Reverse().ToArray();
            return result;
        }
    }

    /// <summary>
    ///     The cyclic dependency exception.
    /// </summary>
    public class CyclicDependencyException : Exception
    {
        /// <summary>
        ///     Initializes a new instance of the <see cref="CyclicDependencyException" /> class.
        /// </summary>
        public CyclicDependencyException()
            : base("Cyclic dependency detected")
        {
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="CyclicDependencyException"/> class.
        /// </summary>
        /// <param name="message">
        /// The message.
        /// </param>
        public CyclicDependencyException(string message)
            : base(message)
        {
        }
    }

    /// <summary>
    ///     The topological sorter.
    /// </summary>
    internal class TopologicalSorter
    {
        #region Ctor

        /// <summary>
        /// Initializes a new instance of the <see cref="TopologicalSorter"/> class.
        /// </summary>
        /// <param name="size">
        /// The size.
        /// </param>
        public TopologicalSorter(int size)
        {
            this._vertices = new int[size];
            this._matrix = new int[size, size];
            this._numVerts = 0;
            for (var i = 0; i < size; i++)
            {
                for (var j = 0; j < size; j++)
                {
                    this._matrix[i, j] = 0;
                }
            }

            this._sortedArray = new int[size]; // sorted vert labels
        }

        #endregion

        #region Private Members

        /// <summary>
        ///     The _vertices.
        /// </summary>
        private readonly int[] _vertices; // list of vertices

        /// <summary>
        ///     The _matrix.
        /// </summary>
        private readonly int[,] _matrix; // adjacency matrix

        /// <summary>
        ///     The _num verts.
        /// </summary>
        private int _numVerts; // current number of vertices

        /// <summary>
        ///     The _sorted array.
        /// </summary>
        private readonly int[] _sortedArray;

        #endregion

        #region Public Methods

        /// <summary>
        /// The add vertex.
        /// </summary>
        /// <param name="vertex">
        /// The vertex.
        /// </param>
        /// <returns>
        /// The <see cref="int"/>.
        /// </returns>
        public int AddVertex(int vertex)
        {
            this._vertices[this._numVerts++] = vertex;
            return this._numVerts - 1;
        }

        /// <summary>
        /// The add edge.
        /// </summary>
        /// <param name="start">
        /// The start.
        /// </param>
        /// <param name="end">
        /// The end.
        /// </param>
        public void AddEdge(int start, int end)
        {
            this._matrix[start, end] = 1;
        }

        /// <summary>
        ///     The sort.
        /// </summary>
        /// <returns>
        ///     The <see cref="int[]" />.
        /// </returns>
        /// <exception cref="CyclicDependencyException">
        /// </exception>
        public int[] Sort()
        {
            // topological sort
            while (this._numVerts > 0)
            {
                // while vertices remain,
                // get a vertex with no successors, or -1
                var currentVertex = this.NoSuccessors();
                if (currentVertex == -1)
                {
                    // must be a cycle                
                    throw new CyclicDependencyException();
                }

                // insert vertex label in sorted array (start at end)
                this._sortedArray[this._numVerts - 1] = this._vertices[currentVertex];

                this.DeleteVertex(currentVertex); // delete vertex
            }

            // vertices all gone; return sortedArray
            return this._sortedArray;
        }

        #endregion

        #region Private Helper Methods

        // returns vert with no successors (or -1 if no such verts)
        /// <summary>
        ///     The no successors.
        /// </summary>
        /// <returns>
        ///     The <see cref="int" />.
        /// </returns>
        private int NoSuccessors()
        {
            for (var row = 0; row < this._numVerts; row++)
            {
                var isEdge = false; // edge from row to column in adjMat
                for (var col = 0; col < this._numVerts; col++)
                {
                    if (this._matrix[row, col] > 0)
                    {
                        // if edge to another,
                        isEdge = true;
                        break; // this vertex has a successor try another
                    }
                }

                if (!isEdge)
                {
                    // if no edges, has no successors
                    return row;
                }
            }

            return -1; // no
        }

        /// <summary>
        /// The delete vertex.
        /// </summary>
        /// <param name="delVert">
        /// The del vert.
        /// </param>
        private void DeleteVertex(int delVert)
        {
            // if not last vertex, delete from vertexList
            if (delVert != this._numVerts - 1)
            {
                for (var j = delVert; j < this._numVerts - 1; j++)
                {
                    this._vertices[j] = this._vertices[j + 1];
                }

                for (var row = delVert; row < this._numVerts - 1; row++)
                {
                    this.MoveRowUp(row, this._numVerts);
                }

                for (var col = delVert; col < this._numVerts - 1; col++)
                {
                    this.MoveColLeft(col, this._numVerts - 1);
                }
            }

            this._numVerts--; // one less vertex
        }

        /// <summary>
        /// The move row up.
        /// </summary>
        /// <param name="row">
        /// The row.
        /// </param>
        /// <param name="length">
        /// The length.
        /// </param>
        private void MoveRowUp(int row, int length)
        {
            for (var col = 0; col < length; col++)
            {
                this._matrix[row, col] = this._matrix[row + 1, col];
            }
        }

        /// <summary>
        /// The move col left.
        /// </summary>
        /// <param name="col">
        /// The col.
        /// </param>
        /// <param name="length">
        /// The length.
        /// </param>
        private void MoveColLeft(int col, int length)
        {
            for (var row = 0; row < length; row++)
            {
                this._matrix[row, col] = this._matrix[row, col + 1];
            }
        }

        #endregion
    }
}